package test;
/*题目
124. 二叉树中的最大路径和
给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

数据
输入：[1,2,3]

       1
      / \
     2   3

输出：6
输入：[-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出：42
*/

import bean.TreeNode;

public class letcode124_zuidalujin {
    public static Integer sum=Integer.MIN_VALUE;   //初始化足够小
    //计算node可提供给父节点最大值  后序遍历  时间复制度为o(n)  空间复杂度也为o(n)
    public static  int maxPathSum(TreeNode root){
        if(root==null) return 0;
        int lv=Math.max(maxPathSum(root.left),0);
        int rv=Math.max(maxPathSum(root.right),0);   //判断拿到的值是否大于0，小于0就取0
         sum=Math.max(root.val+lv+rv,sum);  //不穿过父节点，只穿过本身
         return root.val+Math.max(lv,rv);    //需要穿过父节点的办法
    }

    public static void main(String[] args) {
        TreeNode t=new TreeNode(1);
        TreeNode t1=new TreeNode(2);
        TreeNode t2=new TreeNode(3);
        TreeNode t3=new TreeNode(4);
        TreeNode t4=new TreeNode(5);
        TreeNode t5=new TreeNode(6);
        TreeNode t6=new TreeNode(7);
        t.left=t1;
        t.right=t2;
        t1.left=t3;
        t1.right=t4;
        t2.right=t5;
        t4.left=t6;
        maxPathSum(t);
        System.out.println(sum);
    }
}
